package org.algorithm.BinarySearch;

public class BinarySearch
{
    /**
     * 二分查找
     * @param arr
     * @param target
     * @return
     */

    //左闭右闭
    public static int binarySearchBasic(int []arr,int target)
    {
        int left = 0,right =arr.length-1;

        while (left<=right)
        {
            int mid = (left+right)>>>1;

            if (target>arr[mid])
            {
                left=mid+1;
            }else if (target<arr[mid])
            {
                right=mid-1;
            }else {
                return mid;
            }
        }

        return -1;
    }

    //左闭右开
    public static int binarySearchBasic2(int []arr,int target)
    {
        int left = 0,right = arr.length;

        while (left<right)
        {
            int mid = (left+right)>>>1;

            if (target<arr[mid])
            {
                right=mid;
            }else if (arr[mid]<target)
            {
                left=mid+1;
            }else {
                return mid;
            }
        }

        return -1;
    }

    //平衡二分查找
    //左闭右开
    public static int binarySearchBasic3(int []arr,int target)
    {
        int left =0,right = arr.length;

        while (1<right-left)
        {
            int mid =(left+right)>>>1;

            if (target<arr[mid])
            {
                right=mid;
            }else {
                left=mid;
            }
        }

        if (arr[left]==target)
        {
            return left;
        }else {
            return -1;
        }
    }

    //查找数组中重复的最左侧的元素索引
    public static int binarySearchLeftmost1(int []arr,int target)
    {
        int left = 0,right =arr.length-1;

        int candidate = -1;

        while (left<=right)
        {
            int mid = (left+right)>>>1;

            if (target<arr[mid])
            {
                right=mid-1;
            }else if (arr[mid]<target)
            {
                left=mid+1;
            }else {
                //记录候选的位置
                candidate=mid;
                right=mid-1;
            }
        }

        return candidate;
    }

    public static int binarySearchLeftmost2(int []arr,int target)
    {
        int left = 0,right =arr.length-1;

        while (left<=right)
        {
            int mid = (left+right)>>>1;

            if (target<=arr[mid])
            {
                right=mid-1;
            }else
            {
                left=mid+1;
            }
        }

        return left;
    }

    //查找数组中重复的最右侧的元素索引
    public static int binarySearchRightmost1(int []arr,int target)
    {
        int left = 0,right =arr.length-1;

        int candidate = -1;

        while (left<=right)
        {
            int mid = (left+right)>>>1;

            if (target<arr[mid])
            {
                right=mid-1;
            }else if (arr[mid]<target)
            {
                left=mid+1;
            }else {
                //记录候选的位置
                candidate=mid;
                left=mid+1;
            }
        }

        return candidate;
    }

    public static int binarySearchRightmost2(int []arr,int target)
    {
        int left = 0,right =arr.length-1;


        while (left<=right)
        {
            int mid = (left+right)>>>1;

            if (target<arr[mid])
            {
                right=mid-1;
            } else {
                left=mid+1;
            }
        }

        return left-1;
    }


    public static void main(String[] args) {
//        int a []={7,13,21,30,38};
//
//        int index = binarySearchBasic3(a, 30);
//        System.out.println(index);


        int b []={7,13,13,21,30,30,38};
        int index2 = binarySearchLeftmost2(b, 13);
        index2=index2-1;
        System.out.println("前任："+index2);
        int index3 = binarySearchRightmost2(b, 13);
        index3=index3+1;
        System.out.println("后任："+index3);
    }
}
